from typing import *


class Solution:

    def maximumSetSize(self, nums1: List[int], nums2: List[int]) -> int:
        h = {}
        for v in nums1:
            if v in h:
                h[v][0] += 1
            else:
                h[v] = [1, 0]
        for v in nums2:
            if v in h:
                h[v][1] += 1
            else:
                h[v] = [0, 1]
        t1 = t2 = 0
        for k, (v1, v2) in h.items():
            t1 += max(v1 - 1, 0)
            t2 += max(v2 - 1, 0)
        s = [[v1, v2] for k, (v1, v2) in h.items()]
        n = len(nums1) // 2

        def f(t, a, b):
            i = 0
            while t < n and i < len(s):
                while i < len(s):
                    if s[i][a] > 0 and s[i][b] > 0:
                        s[i][a] = 0
                        t += 1
                        i += 1
                        break
                    i += 1
            i = 0
            while t < n and i < len(s):
                while i < len(s):
                    if s[i][a] > 0:
                        s[i][a] = 0
                        t += 1
                        i += 1
                        break
                    i += 1

        f(t1, 0, 1)
        f(t2, 1, 0)
        ans = 0
        for a, b in s:
            if a > 0 or b > 0:
                ans += 1
        return ans


class Solution:

    def maximumSetSize(self, nums1: List[int], nums2: List[int]) -> int:
        s1, s2 = set(nums1), set(nums2)
        s = s1 & s2
        n1, n2, c = len(s1), len(s2), len(s)
        ans = n1 + n2 - c
        m = len(nums1) // 2
        sc = 0
        if n1 > m:
            d = min(n1 - m , c)
            ans -= n1 - m - d 
            c -= d
        if n2 > m:
            ans -= n2 - m - min(n2 - m , c)
        return ans


s = Solution()
print(s.maximumSetSize(nums1=[1, 2, 3, 4, 5, 6], nums2=[2, 3, 2, 3, 2, 3]))
# print(s.maximumSetSize(nums1=[1, 2, 1, 2], nums2=[1, 1, 1, 1]))
